The present disclosure relates generally to polynomial-generated error-correcting encoding and decoding and, more specifically, to Reed-Solomon (RS) error detection and correction techniques for example concatenated convolutional RS decoding.
Reed-Solomon coding and decoding schemes are used in many communication systems, such as satellites, modems, audio compact discs and wireless telephones. Each communication system has a different set of values for the parameters which define the Reed-Solomon code. Reed-Solomon encoders/decoders use Galois Field (GF) arithmetic to map blocks of communication into larger blocks.
As implemented in hardware, the Reed-Solomon encoder/decoder requires a substantial number of logic gates and other hardware. Many efforts have been directed to reducing the amount of hardware by, for example, parallel processing and reducing the arithmetic representation of the processes. Reed-Solomon decoders, specific to various communication systems, have been implemented in dedicated hardware blocks because of the computational complexity and low power requirements. See, for example, R. E. Blahut's “Theory and practice of error control codes,” Addison-Wesley, 1984; and S. B. Wicker's “Error control systems for digital communication and storage,” Prentice Hall, Inc., 1995.
One example of an error correction device for a communications system using the Reed-Solomon code is U.S. Pat. No. 6,065,149. The error correction device is provided with an internal code decoder which outputs a series of decoded data and reliability information of the decoded data, a CRC (Cyclic Redundancy Check) decoder, a de-interleaver, an erasure position detector, and an external code decoder for decoding an external code by soft judgment. When the external code is decoded by the soft judgment, not only the series of decoded data of the internal code and their reliability information, but also the frame error information based on CRC are used as input signals. In example described in the patent, one symbol in the Reed-Solomon code is constituted by 8-bits and therefore the Galois field is 256. After CRC decoding, the erasure position detector determines if 8-bits have been erased in 40 symbols. If so, it controls the external code decoder so as to correct the erasure of the 8 symbols. If no frame error is detected by the CRC decoder, the erasure position detector controls the external decoder to perform 4 symbol error correction. Thus, the system either performs corrections of the erasures for 8 symbols or performs 4 symbol error correction based on the results of the CRC decoder.
A similar system for coding and decoding symbols using CRC check bit of a Reed-Solomon code is described in U.S. Pat. No. 6,081,919. The decoding apparatus includes error detection using the CRC check bits performed after decoding of the inner decode. After symbol deinterleaving is performed, decoding of the outer code by erasure decoding or error detection is performed depending upon the number of symbols included in a frame in which an error has been detected. If the number of symbols in a frame after deinterleaving in which errors have been detected is not larger than the number of symbols which can be corrected by the erasure decoding, the decoding of the outer code is done by erasure decoding. If the number of symbols in the frame after deinterleaving which have detected errors is larger than the number of symbols which can be corrected by the erasure decoding, than the outer code is decoded by error correction. As in the previous patent, this is a system that performs either erasure decoding or error correction decoding.
The present system is a method and apparatus for decoding an encoded data stream of bits using an inner decoder, deinterleaver and an outer decoder. The outer decoder first decodes by error correction decoding for r errors per word. The decoding is terminated and a decoded word is outputted if the syndromes of the corrected word of the first decoding are all zeros. If the syndromes of the corrected word of the first decoding are not all zeros, a second decoding is performed by error correcting and erasure decoding for the number of errors r reduced by one and the number of erasures increased by two. The decoding is terminated and a decoded word is outputted if the syndromes of the corrected word of the second decoding are all zeros. If the syndromes of the corrected word of the second decoding are not all zeros, the second decoding by error correcting and erasure decoding is repeated for the number of errors reduced by one and the number of erasures increased by two for each iteration of the second decoding.
Also, a method and apparatus of decoding includes an inner coder, a deinterleaver and an outer decoder wherein the outer decoder first decodes by error correction for r error per word. The decoding is terminated and a decoded word is outputted if the syndromes of the corrected word of the first decoding are all zeros. If the syndromes of the corrected word of the first decoding are not all zeros, the error r is reduced by one and the number of erasures is increased by two. An error locator polynomial is derived and the degree of the error located polynomial is compared to the decreased number of errors if the syndromes of the corrected word of the first decoding are not all zeros. If the degree of the error locator is greater than the decreased number of errors, the number of errors are decreased by one and the number of erasures are increased by two and the deriving and comparing steps are repeated. If the degree of the error locator is equal to or less than the decreased number of errors, the second decoding by error correcting and erasure decoding is performed.
These and other aspects of the present disclosure will become apparent from the following detailed description of the disclosure, when considered in conjunction with accompanying drawings.